package dynamicProgramming.DoubleSequenceProblem;

/**
 * @author zxc
 * @date 2023/01/22 08:38
 **/

/**
 * 题目 ：最长公共子序列
 * 题目详述 ：
 * 给定两个字符串text1 和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
 * 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
 * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
 *
 * 提示：
 * 1 <= text1.length, text2.length <= 1000
 * text1 和 text2 仅由小写英文字符组成。
 */
public class LongestCommonSubsequence {
    /**
     * 思路 ：
     * 迭代思想，使用二维数组temp来存储迭代过程中结果;
     *
     * 状态转移方程 ：
     * ===》 假设f(i + 1 , j + 1)为子字符串S[0...i]和T[0...j]的最大字符串长度;
     * （1）若是子字符串S的最后一个字符S[i] == 子字符串T的最后一个字符T[j]，
     * ===》 f(i + 1 , j + 1) = f(i , j) + 1;
     * （2）若是子字符串T的最后一个字符T[j] != 子字符串S的最后一个字符S[i],
     * 即，f(i + 1 , j + 1)就取决于f(i + 1 , j)和f(i , j + 1);
     * ===》 f(i + 1 , j + 1) = max(f(i + 1 , j) , f(i , j + 1));
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        /**
         * 为啥需要将temp临时数组设置为 new int[len1 + 1][len2 + 1]大小呢？
         * （1）即，由于i == 0/j == 0所代表的字符串是只包含单个字符的字符串;
         * （2）可能会出现空字符串的情况，所以使用arr[i][0]和arr[0][j]来存储s1字符串为空/s2字符串为空的情况;
         */
        int[][] temp = new int[len1 + 1][len2 + 1];
        // 双层循环 ：来填充temp临时数组（temp数组，用来存储迭代过程中结果）
        for(int i = 0 ; i < len1 ; i++){
            for(int j = 0 ; j < len2 ; j++){
                // 若是当前遍历的子字符串s1和s2的最后一个字符相同的话，
                if(text1.charAt(i) == text2.charAt(j)){
                    // 即，获取两个子字符串s1和s2移除最后一个字符后，所得到的子字符串t1和t2，其对应在temp数组中临时存储的值;
                    temp[i + 1][j + 1] = temp[i][j] + 1;
                }
                else {
                    // 即，若是两个字符串不相同的话，则获取temp[i + 1][j]和temp[i][j + 1])中的最大值;
                    // ===》 temp[i + 1][j] , temp[i][j + 1])两个数组元素，都已经在之前求解并保存过;
                    temp[i + 1][j + 1] = Math.max(temp[i + 1][j] , temp[i][j + 1]);
                }
            }
        }
        // 返回，即直接返回temp数组最后一个元素即可;
        return temp[len1][len2];
    }
}
